1. Field of Invention
The present invention relates generally to the field of solving a system of linear equations. More specifically, the present invention is related to a computer-based method and a system for solving a large sparse triangular system of linear equations.
2. Discussion of Prior Art
Most natural phenomenon are modeled or simulated using a system of linear equations. Solving linear equations can be computationally intensive depending on the dimensions of the matrices involved.
FIG. 1 illustrates a general method of solving a system of linear equations and is given by:
Ax=bxe2x80x83xe2x80x83(1) 
Matrix 106 (of dimension nxc3x97n) represents the array or matrix representative of vector A; matrix 108 represents the array or matrix representative of vector x (of dimension 1xc3x97n); and array or matrix 110 represents the array or matrix representative of vector b (of dimension 1xc3x97n). Solving the system of linear equations of (1) in terms of x as given below:
x=Axe2x88x921b=Wbxe2x80x83xe2x80x83(2) 
where
xe2x80x83W=Axe2x88x921xe2x80x83xe2x80x83(3)
Equation (2) provides for a solution to the system of linear equations given by 100. Thus, the system of linear equations, in matrix form, given by 100 can be rewritten, as in 102, in terms of the matrix or array representative of x, wherein the matrix given by 112 is the inverse of A, denoted Axe2x88x921. The inverse of matrix A or Axe2x88x921 112 can further be presented and replaced by another matrix W 114 as in (3). The computation of x as described in 104 represents a solution to the system of linear equations given by (1) and as the dimension n of the matrices involved (108, 114, and 110) increases, so does the computational overhead of a processor trying to perform that operation.
Sparse matrices (i.e., very few non-zero elements) arise more frequently than dense matrices (i.e., very few zero elements). An example of a general structure of a sparse 4xc3x974 square matrix is given below:                     S        =                  ⌊                                                                      s                  11                                                            0                                            0                                                              s                  14                                                                                    0                                            0                                            0                                            0                                                                    0                                            0                                            0                                                              s                  34                                                                                    0                                            0                                            0                                            0                                              ⌋                                    (        4        )            
wherein the elements s11, s14, and s34 are the only non-zero elements in (4). The diagonal of a square matrix (nxc3x97n) divides it into two halves and helps define two kinds of sparse matrices: upper-triangular or lower triangular. If the block below the diagonal consists of zeros, the matrix is said to be upper triangular. For example, the matrix shown below is upper triangular:                     U        =                  ⌊                                                    0                                                              s                  12                                                            0                                                              s                  14                                                                                    0                                            0                                            0                                            0                                                                    0                                            0                                            0                                                              s                  34                                                                                    0                                            0                                            0                                            0                                              ⌋                                    (        5        )            
In contrast to (5), if the block above the diagonal consists of zeros, then the matrix is said to be lower-triangular. An example of a lower triangular matrix is shown below:                     L        =                  ⌊                                                    0                                            0                                            0                                            0                                                                    0                                            0                                            0                                            0                                                                    0                                                              s                  32                                                            0                                            0                                                                                      s                  41                                                            0                                            0                                            0                                              ⌋                                    (        6        )            
Matrices that are representative of a system of linear equations that simulate real life phenomenon are usually either lower (5) or upper (6) triangular and the traditional methods of solving such equations create undue computational burden on the processor. Standard methods of solving each systems may take too much time since they do not take advantage of the presence of many zero entries in a sparse matrix. Thus, they handle each entry of the sparse matrix in sequence, and generate the entries of the solution matrix, x in the case of (2), one at a time, even though many or most of them may be equal to zero. Therefore, there is a need for a system which overcomes the shortcomings of prior methods (that perform more than necessary computations) and utilizes only the non-zero components of a matrix to solve large sparse triangular linear equations and generate explicitly only the non-zero entries of the solution.
Whatever the precise merits, features and advantages of prior methods, none of them achieve or fulfills the purposes of the present invention. The current invention provides for a system that takes advantage of sparse structure of matrices (upper or lower triangular) and maintains an ordered data structure and a pair of ordered vectors that contains only the non-zero indices, their respective values, and pointers to these values. Thus the invention teaches how to solve the system more efficiently without generating zero entries of the solution explicitly. These and other objects are achieved by the detailed description that follows.
The present invention provides for a computer-based system and a method for solving a large sparse triangular system of linear equations. The invention utilizes only the non-zero components of a matrix to solve large sparse triangular linear equations and generates explicitly only the non-zero entries of the solution.
The computer-based method and system comprises three data structures: partially ordered data structure (or simply ordered data structure), contiguous list v, and vector p. A list of the row indices of the known non-zero values of x which require farther processing is stored in the ordered data structure. Actual non-zero values of x are stored in the contiguous list v and the corresponding pointers to the location of these values are stored in the vector p. The present invention manipulates these three matrices to find a solution to an upper or lower sparse triangular system of linear equations. In addition, the present invention also takes into account the case wherein a matrix becomes dense (or increases in density) by the presence of many active rows. A partitioning method is described via which the dense matrix problem is solved.